{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 贪心法的作业"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 16.1-4\n",
    "首先把所有的开始时间和结束时间排序。新建两个列表free和occupied，遍历这个时间数组，如果遍历到开始时间且free数组不为空，那么把其中一个元素转移到occupied之中，否则新建一个教室编号并加入occupied。如果遍历到结束时间，把occupied中的元素转移到free中。代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "教室总数：1\n",
      "时间：['1', '2']\n",
      "教室的最低数量：1\n"
     ]
    }
   ],
   "source": [
    "n = int(input())  # 活动的总数\n",
    "print(\"教室总数：{}\".format(n))\n",
    "time = []  # 所有的时间\n",
    "free = []  # 存储空教室的编号\n",
    "occupied = {}  # 存储占用教室的编号和活动\n",
    "classroom_num = 0\n",
    "for i in range(n):\n",
    "    s = input().split()\n",
    "    print(\"时间：{}\".format(s))\n",
    "    time.append((int(s[0]), i, 0))  # 0表示开始时间  (时间、活动的编号、开始/结束)\n",
    "    time.append((int(s[1]), i, 1))  # 1表示结束时间  (时间、活动的编号、开始/结束)\n",
    "\n",
    "time = sorted(time, key=lambda x: x[0])  # 时间排序\n",
    "\n",
    "for (_, a, m) in time:  # (时间、活动的编号、开始/结束)\n",
    "    if m == 0:  # 开始时间\n",
    "        if len(free) != 0:  # 有空闲教室\n",
    "            classroom = free[-1]\n",
    "            free.pop(-1)\n",
    "            occupied[a] = classroom  # 教室编号、结束时间\n",
    "        else:  # 无空闲教室\n",
    "            occupied[a] = classroom_num\n",
    "            classroom_num += 1\n",
    "    else:  # 结束时间\n",
    "        free.append(occupied[a])\n",
    "        del(occupied[a])\n",
    "\n",
    "print(\"教室的最低数量：{}\".format(classroom_num))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 16.2-7\n",
    "将$A$、$B$数组全部按相同顺序（升序或者降序）排列后的收益最大。 \n",
    "\n",
    "证明：  \n",
    "由于函数$f(x)=lnx$是单调递增的，所以对收益取对数不影响极大值的取法。  \n",
    "设$$W \\overset{\\text{def}}{=} \\prod_{i=1}^{n} a_i^{b_i}$$\n",
    "则$$ lnW = \\sum_{i=1}^{n} b_i ln(a_i) $$\n",
    "由排序不等式，知当$a_i$,$b_i$排好序后，有（顺序和大于等于乱序和大于等于逆序和）$$ \\sum_{i=1}^{n} b_i ln(a_i) \\geq \\sum_{i=1}^{n} b_{k_i} ln(a_i) \\geq \\sum_{i=1}^{n} b_{n-i} ln(a_i) $$\n",
    "所以$A$、$B$数组全部按相同顺序排好序后顺序和$\\sum_{i=1}^{n} b_i ln(a_i)$是最大的，这样收益也是最大的。   \n",
    "Q.E.D.  \n",
    "\n",
    "设$A$、$B$数组的长度为$m$、$n$，则运行时间是$\\varTheta (mlgm+nlgn)$的。\n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A:[1, 3, 7, 5, 9]\n",
      "B:[2, 4, 8, 6, 20, 10]\n",
      "收益：3492564909\n"
     ]
    }
   ],
   "source": [
    "A_str = input().split()\n",
    "B_str = input().split()\n",
    "A = [int(i) for i in A_str]\n",
    "B = [int(i) for i in B_str]\n",
    "print(\"A:{}\".format(A))\n",
    "print(\"B:{}\".format(B))\n",
    "A.sort()\n",
    "B.sort()\n",
    "ans = sum(map(lambda a, b: a**b, A, B))\n",
    "print(\"收益：{}\".format(ans))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 16.3-3\n",
    "哈夫曼树如下：  \n",
    "<img src=\"./images/16.3-3.svg\" width=20%>    \n",
    "哈夫曼编码：\n",
    "+ a:0000000\n",
    "+ b:0000001\n",
    "+ c:000001\n",
    "+ d:00001\n",
    "+ e:0001\n",
    "+ f:001\n",
    "+ g:01\n",
    "+ h:1\n",
    "\n",
    "推广：对于前n个斐波那契数的编码，有\n",
    "$$\n",
    "a_i:\\left\\{\n",
    "    \\begin{align*}\n",
    "    & 0\\dots 0 (n-1个0) (i = 1) \\\\\n",
    "    & 0\\dots 01 (n-i个0) (i\\neq 1)\n",
    "    \\end{align*}\n",
    "    \\right .\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 16-1\n",
    "### a\n",
    "贪心策略是尽量取面额大的。      \n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n:40\n",
      "最少使用3枚硬币\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "print(\"n:{}\".format(n))\n",
    "m_list = [25, 10, 5, 1]\n",
    "ans = 0\n",
    "for m in m_list:\n",
    "    if n == 0:\n",
    "        break\n",
    "    ans += n//m\n",
    "    n %= m\n",
    "print(\"最少使用{}枚硬币\".format(ans))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### b\n",
    "贪心策略是尽量取面额大的。    \n",
    "证明：  \n",
    "（反证法）设\n",
    "$$\\{a_i\\}_{1}^{k}$$\n",
    "为贪心法算出的解，\n",
    "$$\\{b_i\\}_{1}^{k}$$\n",
    "是最优解，\n",
    "且\n",
    "$$\\{a_i\\}_{1}^{k}\\neq\\{b_i\\}_{1}^{k}$$\n",
    "那么有\n",
    "$$\\sum_{i=0}^{k} a_i c^i =n$$\n",
    "$$\\sum_{i=0}^{k} b_i c^i =n$$\n",
    "$$\\sum_{i=0}^{k} a_i > \\sum_{i=0}^{k} b_i$$\n",
    "由于$\\{a_i\\}_{1}^{k}$\n",
    "实际上是$n$的$k$进制展开，且$\\forall i,a_i<k$。由整数$k$进制表示的唯一性，若$\\{a_i\\}_{1}^{k}\\neq\\{b_i\\}_{1}^{k}$，则$\\exists j,b_j\\geq k$。\n",
    "那么对应的$b_j c^j$可以写成\n",
    "$$b_j c^j = rc^{j+1}+qc$$\n",
    "由于$c>1$，所以$b_j>r+q$。  那么做此调整后，$\\sum_{i=0}^{k} b_i$减小，这和$\\{b_i\\}_{1}^{k}$是最优解矛盾。\n",
    "所以$\\{a_i\\}_{1}^{k}$就是最优解。   \n",
    "Q.E.D.   \n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "c:2,k:2,n:7\n",
      "最少使用3枚硬币\n"
     ]
    }
   ],
   "source": [
    "c = int(input())\n",
    "k = int(input())\n",
    "n = int(input())\n",
    "print(\"c:{},k:{},n:{}\".format(c, k, n))\n",
    "ans = 0\n",
    "while n > 0:\n",
    "    ans += n % k\n",
    "    n //= k\n",
    "print(\"最少使用{}枚硬币\".format(ans))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### c\n",
    "取c = [4,3,1], n = 6  \n",
    "贪心法计算得$6=1\\times 4+2\\times 1$，需要3枚硬币。\n",
    "而实际$6=2\\times 3$，需要2枚硬币。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### d\n",
    "这是一个完全背包问题，可以使用动态规划计算。  \n",
    "设$dp[i][j]$表示使用$c_1\\dots c_i$硬币找零$j$元钱的最优解。\n",
    "状态转移方程：\n",
    "$$dp[i][j]=min_{0\\leq k\\leq \\lceil j/c_i \\rceil} (dp[i-1][j], dp[i][j-k\\times c_i]+k)$$\n",
    "可以进行状态压缩优化，优化后有：\n",
    "$$dp[j] = min(dp[j - c_i]+1,dp[j])$$\n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n:6,c:[4, 3, 1]\n",
      "最少使用2枚硬币\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "c_str = input().split()\n",
    "c = [int(i) for i in c_str]\n",
    "print(\"n:{},c:{}\".format(n, c))\n",
    "c.insert(0, 0)\n",
    "# 初始化dp数组\n",
    "dp = [float(\"inf\") if i != 0 else 0 for i in range(1+n)]\n",
    "# 状态转移\n",
    "for i in range(1, len(c)):\n",
    "    for j in range(c[i], 1+n):\n",
    "        dp[j] = min(dp[j-c[i]]+1, dp[j])\n",
    "print(\"最少使用{}枚硬币\".format(dp[n]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 附加\n",
    "0-1背包问题，使用动态规划。  \n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最大价值是11\n"
     ]
    }
   ],
   "source": [
    "n = 7\n",
    "V = 15\n",
    "v = [10, 5, 15, 7, 6, 18, 3]\n",
    "w = [2, 3, 5, 7, 1, 4, 1]\n",
    "dp = [0 for _ in range(1 + V)]\n",
    "for i in range(n):\n",
    "    for j in range(V, v[i]-1, -1):\n",
    "        dp[j] = max(w[i]+dp[j-v[i]], dp[j])\n",
    "print(\"最大价值是{}\".format(max(dp)))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.2 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2 (tags/v3.10.2:a58ebcc, Jan 17 2022, 14:12:15) [MSC v.1929 64 bit (AMD64)]"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a166369db42c1466e2e3775def9041c304cd3bfe227c8b0f35b781bd0a6af835"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
